package nk.tree;

import java.util.HashMap;
import java.util.HashSet;

public class AB17 {
    HashMap<Integer, Integer> map = new HashMap();

    public TreeNode buildTree (int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return getTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode getTree(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) {
        if (il < 0 || ir >= inorder.length || pl < 0 || pr >= postorder.length || il > ir || pl > pr)
            return null;

        if (il == ir) {
            TreeNode node = new TreeNode(inorder[il]);
            return node;
        }
        TreeNode node = new TreeNode(postorder[pr]);
        int index = map.get(postorder[pr]); //根节点在中序遍历序列中的下标
        node.left = getTree(inorder, il, index - 1, postorder, pl, pl + index - il - 1);
        node.right = getTree(inorder, index + 1, ir, postorder, pl + index - il, pr - 1);
        return node;
    }


    public static void main(String[] args) {

        AB17 ab17 = new AB17();
        int[] in = {5,4,3,2,1};
        int[] po = {5,4,3,2,1};
        TreeNode treeNode = ab17.buildTree(in, po);
    }

}

class TreeNode {
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;
  public TreeNode(int val) {
    this.val = val;
  }
}